import java.util.*;

class Solution127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> hash = new HashSet<>();
        Set<String> used = new HashSet<>();
        for (String str : wordList) {
            hash.add(str);
        }
        if (beginWord.equals(endWord)) {
            return 0;
        }
        if (!hash.contains(endWord)) {
            return 0;
        }

        // 开始bfs
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        used.add(beginWord);
        // 记录最短路径
        int len = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            len++ ;
            for (int i = 0; i < size; i++) {
                String tmp = queue.poll();
                for (int j = 0; j < tmp.length(); j++) {
                    char[] arr = tmp.toCharArray();
                    for (int z = 0; z < 26; z++) {
                        arr[j] = (char) (z + 'a');
                        String ret = new String(arr);
                        if (hash.contains(ret) && !used.contains(ret)) {
                            queue.add(ret);
                            used.add(ret);
                        }
                        if (ret.equals(endWord)) {
                            return len;
                        }
                    }

                }

            }
        }

        return 0;
    }
}